{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #寻找二叉树的最近公共祖先"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: lowestCommonAncestor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的最近公共祖先"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。</p>\n",
    "\n",
    "<p><a href=\"https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88/8918834?fr=aladdin\" target=\"_blank\">百度百科</a>中最近公共祖先的定义为：&ldquo;对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（<strong>一个节点也可以是它自己的祖先</strong>）。&rdquo;</p>\n",
    "\n",
    "<p>例如，给定如下二叉树:&nbsp; root =&nbsp;[3,5,1,6,2,0,8,null,null,7,4]</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/15/binarytree.png\"></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释: </strong>节点 <code>5 </code>和节点 <code>1 </code>的最近公共祖先是节点 <code>3。</code>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4\n",
    "<strong>输出:</strong> 5\n",
    "<strong>解释: </strong>节点 <code>5 </code>和节点 <code>4 </code>的最近公共祖先是节点 <code>5。</code>因为根据定义最近公共祖先节点可以为节点本身。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>说明:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>所有节点的值都是唯一的。</li>\n",
    "\t<li>p、q 为不同节点且均存在于给定的二叉树中。</li>\n",
    "</ul>\n",
    "\n",
    "<p>注意：本题与主站 236 题相同：<a href=\"https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/\">https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof](https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof](https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        candidates = []\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            candidates.append(cur)\n",
    "            if cur is p or cur is q:\n",
    "                break\n",
    "            if cur.left:\n",
    "                queue.append(cur.left)\n",
    "            if cur.right:\n",
    "                queue.append(cur.right)\n",
    "        \n",
    "        for i in range(len(candidates)-1, -1, -1):\n",
    "            queue = deque([candidates[i]])\n",
    "            flag_p = False\n",
    "            flag_q = False\n",
    "            while queue:\n",
    "                cur = queue.popleft()\n",
    "                flag_p = True if cur is p else flag_p\n",
    "                flag_q = True if cur is q else flag_q\n",
    "                if cur.left:\n",
    "                    queue.append(cur.left)\n",
    "                if cur.right:\n",
    "                    queue.append(cur.right)\n",
    "            if flag_p and flag_q:\n",
    "                return candidates[i]\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        pre = {}\n",
    "        stack = [(root, None)]\n",
    "        while stack:\n",
    "            node, parent = stack.pop()\n",
    "            pre[node] = parent\n",
    "            if node.left:\n",
    "                stack.append([node.left, node])\n",
    "            \n",
    "            if node.right:\n",
    "                stack.append([node.right, node])\n",
    "\n",
    "        def get_path(cur):\n",
    "            path = []\n",
    "            while cur:\n",
    "                path.append(cur)\n",
    "                cur = pre[cur]\n",
    "            return path[::-1]\n",
    "\n",
    "        path1, path2 = get_path(p), get_path(q)\n",
    "        ans = path1[0]\n",
    "        for i, j in zip(path1, path2):\n",
    "            if i != j:\n",
    "                break\n",
    "            ans = i \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        ps = []\n",
    "        qs = []  \n",
    "        if not root:\n",
    "            return None\n",
    "        dq:deque[tuple[TreeNode, List[TreeNode]]] = deque()\n",
    "        dq.append((root, [root]))\n",
    "        while dq:\n",
    "            temp = dq.popleft()\n",
    "            if p == temp[0]:\n",
    "                ps = temp[1]\n",
    "            if q == temp[0]:\n",
    "                qs = temp[1]\n",
    "            if ps and qs:\n",
    "                break\n",
    "            if temp[0].left:\n",
    "                dq.append((temp[0].left,temp[1]+[temp[0].left]))\n",
    "            if temp[0].right:\n",
    "                dq.append((temp[0].right,temp[1]+[temp[0].right]))\n",
    "        for i in range(len(ps)-1, -1, -1):\n",
    "            if ps[i] in qs:\n",
    "                return ps[i]\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        nodes = [root]\n",
    "        parents = {}\n",
    "        while nodes:\n",
    "            n = nodes.pop()\n",
    "            if n.left:\n",
    "                parents[n.left.val] = n\n",
    "                nodes.append(n.left)\n",
    "            if n.right:\n",
    "                parents[n.right.val] = n\n",
    "                nodes.append(n.right)\n",
    "        \n",
    "        visited = {}\n",
    "        tp = p\n",
    "\n",
    "\n",
    "        while tp.val in parents:\n",
    "            if parents[tp.val].val == q.val:\n",
    "                return q\n",
    "            tp = parents[tp.val]\n",
    "            visited[tp.val] = True\n",
    "        while q.val in parents:\n",
    "            if parents[q.val].val == p.val:\n",
    "                return p\n",
    "            q = parents[q.val]\n",
    "            if q.val in visited:\n",
    "                return q\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        depth = 1\n",
    "        dic = dict()\n",
    "        dic[root] = (None, depth)\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            if n: depth += 1\n",
    "            for i in range(n):\n",
    "                node = queue.popleft()\n",
    "                if node.left: \n",
    "                    dic[node.left] = (node, depth)\n",
    "                    queue.append(node.left)\n",
    "                if node.right: \n",
    "                    dic[node.right] = (node, depth)\n",
    "                    queue.append(node.right)\n",
    "        \n",
    "        while dic[q][1] > dic[p][1]:\n",
    "            q = dic[q][0]\n",
    "        while dic[q][1] < dic[p][1]:\n",
    "            p = dic[p][0]\n",
    "        while p.val != q.val:\n",
    "            p = dic[p][0]\n",
    "            q = dic[q][0]\n",
    "        return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root: return root\n",
    "        tmp = []\n",
    "        pre, flag, index = 999999999, 0, 0\n",
    "        tmp.append([root, pre])\n",
    "        while 1:\n",
    "            cur, pre = tmp[index]\n",
    "            index += 1\n",
    "            if cur.left:\n",
    "                tmp.append([cur.left, cur.val])\n",
    "            if cur.right:\n",
    "                tmp.append([cur.right, cur.val])\n",
    "            if cur == p or cur == q: flag += 1\n",
    "            if flag == 2: break\n",
    "        # 看tmp的数据结构\n",
    "        mydict = dict()\n",
    "        for i in tmp:\n",
    "            mydict[i[0].val] = i[1]\n",
    "        # print(mydict)\n",
    "        prep, preq = [p.val], [q.val]\n",
    "        i, j = mydict[p.val], mydict[q.val]\n",
    "        while i != 999999999:\n",
    "            prep.insert(0, i)\n",
    "            i = mydict[i]\n",
    "        while j != 999999999:\n",
    "            preq.insert(0, j)\n",
    "            j = mydict[j]\n",
    "        # index = min(len(prep),len(preq))-1\n",
    "\n",
    "        index = 0\n",
    "        while index < min(len(prep), len(preq)) and prep[index] == preq[index]:\n",
    "            index += 1\n",
    "        # print(prep,preq)\n",
    "        ans = prep[index - 1]\n",
    "        for i in tmp:\n",
    "            if i[0].val == ans: return i[0]\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Run DFS and record each node's parent node. \n",
    "    Start from p, go up to the root node. Mark each node on the way as an ancestor of p. \n",
    "    Start from q, go up to the root node. If reached an ancestor of p, return the ancestor. \n",
    "    Time complexity: O(n). Space complexity: O(n). \n",
    "    '''\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        parent = { root: None }\n",
    "        s = [root]\n",
    "        while len(s) != 0:\n",
    "            cur = s.pop()\n",
    "            if cur.left != None:\n",
    "                parent[cur.left] = cur\n",
    "                s.append(cur.left)\n",
    "            if cur.right != None:\n",
    "                parent[cur.right] = cur\n",
    "                s.append(cur.right)\n",
    "        \n",
    "        ancestorOfP = set()\n",
    "        while p != None:\n",
    "            ancestorOfP.add(p)\n",
    "            p = parent[p]\n",
    "\n",
    "        while q != None:\n",
    "            if q in ancestorOfP:\n",
    "                return q\n",
    "            q = parent[q]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root:return None\n",
    "        \n",
    "        dic = {}\n",
    "        stack = [(1,root)]\n",
    "        has_p,has_q = False,False\n",
    "        while stack:\n",
    "            lv,root = stack.pop()\n",
    "            dic[root] = lv\n",
    "\n",
    "            if root == p:has_p = True\n",
    "            elif root == q:has_q = True\n",
    "            if has_p and has_q:break\n",
    "            if root.left:stack.append((lv*2,root.left))\n",
    "            if root.right:stack.append((lv*2+1,root.right))\n",
    "        \n",
    "        pos_p,pos_q = dic[p],dic[q]\n",
    "        while pos_p!=pos_q:\n",
    "            if pos_p>pos_q:\n",
    "                pos_p//=2\n",
    "            else:\n",
    "                pos_q//=2\n",
    "        for k,v in dic.items():\n",
    "            if v == pos_p:return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root:return None\n",
    "        \n",
    "        dic = {}\n",
    "        stack = [(1,root)]\n",
    "        has_p,has_q = False,False\n",
    "        while stack:\n",
    "            lv,root = stack.pop()\n",
    "            dic[root] = lv\n",
    "\n",
    "            if root == p:has_p = True\n",
    "            elif root == q:has_q = True\n",
    "            if has_p and has_q:break\n",
    "            if root.left:stack.append((lv*2,root.left))\n",
    "            if root.right:stack.append((lv*2+1,root.right))\n",
    "        \n",
    "        pos_p,pos_q = dic[p],dic[q]\n",
    "        while pos_p!=pos_q:\n",
    "            if pos_p>pos_q:\n",
    "                pos_p//=2\n",
    "            else:\n",
    "                pos_q//=2\n",
    "        for k,v in dic.items():\n",
    "            if v == pos_p:return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        dicts = {}\n",
    "        stack = [(1,root)]\n",
    "        has_p,has_q = False,False\n",
    "        while stack:\n",
    "            lv,root = stack.pop()\n",
    "            dicts[root] = lv\n",
    "            if root == p:\n",
    "                has_p = True\n",
    "            elif root == q:\n",
    "                has_q = True\n",
    "                 \n",
    "            if root.right:\n",
    "                stack.append((lv*2+1,root.right))\n",
    "                \n",
    "            if root.left:\n",
    "                stack.append((lv*2,root.left))\n",
    "           \n",
    "            if has_p and has_q:\n",
    "                break\n",
    "        \n",
    "        pos_p,pos_q = dicts[p],dicts[q]\n",
    "        while pos_p!=pos_q:\n",
    "            if pos_p>pos_q:\n",
    "                pos_p//=2\n",
    "            else:\n",
    "                pos_q//=2\n",
    "        for k,v in dicts.items():\n",
    "            if v == pos_p:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        queue = [root]\n",
    "        queue_cache = []\n",
    "        layers = [[root]]\n",
    "        fathers = {}\n",
    "        while queue:\n",
    "            cur_node = queue.pop(0)\n",
    "            if cur_node.left:\n",
    "                fathers[cur_node.left] = cur_node\n",
    "                queue_cache.append(cur_node.left)\n",
    "            if cur_node.right:\n",
    "                fathers[cur_node.right] = cur_node\n",
    "                queue_cache.append(cur_node.right)\n",
    "            if not queue and queue_cache:\n",
    "                queue += queue_cache\n",
    "                layers.append(queue_cache)\n",
    "                queue_cache = []\n",
    "\n",
    "        D_depth = {}\n",
    "        for i, nodes in enumerate(layers):\n",
    "            for node in nodes:\n",
    "                D_depth[node] = i+1\n",
    "\n",
    "        if D_depth[p] < D_depth[q]:\n",
    "            return self.lowestCommonAncestor(root, p, fathers[q])\n",
    "        elif D_depth[p] > D_depth[q]:\n",
    "            return self.lowestCommonAncestor(root, fathers[p], q)\n",
    "        elif p == q:\n",
    "            return p\n",
    "        else:\n",
    "            return self.lowestCommonAncestor(root, fathers[p], fathers[q])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        dicts = {}\n",
    "        stack = [(1,root)]\n",
    "        has_p,has_q = False,False\n",
    "        while stack:\n",
    "            lv,root = stack.pop()\n",
    "            dicts[root] = lv\n",
    "\n",
    "            if root == p:\n",
    "                has_p = True\n",
    "            elif root == q:\n",
    "                has_q = True\n",
    "            if has_p and has_q:\n",
    "                break\n",
    "\n",
    "            if root.right:\n",
    "                stack.append((lv*2+1,root.right))\n",
    "            if root.left:\n",
    "                stack.append((lv*2,root.left))\n",
    "\n",
    "            \n",
    "        \n",
    "        pos_p,pos_q = dicts[p],dicts[q]\n",
    "        while pos_p!=pos_q:\n",
    "            if pos_p>pos_q:\n",
    "                pos_p//=2\n",
    "            else:\n",
    "                pos_q//=2\n",
    "        for k,v in dicts.items():\n",
    "            if v == pos_p:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        dicts = {}\n",
    "        stack = [(1,root)]\n",
    "        has_p,has_q = False,False\n",
    "        while stack:\n",
    "            lv,root = stack.pop()\n",
    "            dicts[root] = lv\n",
    "\n",
    "            if root == p:\n",
    "                has_p = True\n",
    "            elif root == q:\n",
    "                has_q = True\n",
    "            if has_p and has_q:\n",
    "                break\n",
    "\n",
    "            if root.right:\n",
    "                stack.append((lv*2+1,root.right))\n",
    "            if root.left:\n",
    "                stack.append((lv*2,root.left))\n",
    "\n",
    "            \n",
    "        \n",
    "        pos_p,pos_q = dicts[p],dicts[q]\n",
    "        while pos_p!=pos_q:\n",
    "            if pos_p>pos_q:\n",
    "                pos_p//=2\n",
    "            else:\n",
    "                pos_q//=2\n",
    "        for k,v in dicts.items():\n",
    "            if v == pos_p:\n",
    "                return k\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class TreeNode2(TreeNode):\n",
    "    def __init__(self,val ,left=None,right=None,father=None):\n",
    "        self.val=val\n",
    "        self.left=left\n",
    "        self.right=right\n",
    "        self.father=father\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.p,self.q=None,None\n",
    "        head=TreeNode2(root.val)\n",
    "        t1=[root]\n",
    "        t2=[head]\n",
    "        while(len(t1)):\n",
    "            v1,v2=t1[0],t2[0]\n",
    "            t1,t2=t1[1:],t2[1:]\n",
    "\n",
    "            if v1.left:\n",
    "                v2.left=TreeNode2(v1.left.val)\n",
    "                v2.left.father=v2\n",
    "                t1.append(v1.left)\n",
    "                t2.append(v2.left)\n",
    "\n",
    "\n",
    "            if v1.right:\n",
    "                v2.right=TreeNode2(v1.right.val)\n",
    "                v2.right.father=v2\n",
    "                t1.append(v1.right)\n",
    "                t2.append(v2.right)\n",
    "            # print(v1.val,end=' ')\n",
    "            if v1==p:\n",
    "                self.p=v2\n",
    "            if v1==q:\n",
    "                self.q=v2\n",
    "            \n",
    "\n",
    "        p,q=self.p,self.q\n",
    "\n",
    "        res=[p]\n",
    "        # print(p.val,p.father.val,end=' ')\n",
    "\n",
    "        while(p!=head):\n",
    "            p=p.father\n",
    "            res.append(p)\n",
    "\n",
    "\n",
    "        # print(q.val,q.father.val)\n",
    "        while(q!=head):\n",
    "            if q in res:\n",
    "                return q\n",
    "            q=q.father\n",
    "        return head\n",
    "            \n",
    "\n",
    "    \n",
    "    def build(self,root,p,q):\n",
    "\n",
    "        if root==None:\n",
    "            return None\n",
    "\n",
    "        head=TreeNode2(root.val)\n",
    "        if root.left:\n",
    "            head.left=self.build(root.left,p,q)\n",
    "        if root.right:\n",
    "            head.right=self.build(root.right,p,q)\n",
    "        \n",
    "        if root==p:\n",
    "            self.p=head\n",
    "        if root==q:\n",
    "            self.q=head\n",
    "        \n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class TreeNode2(TreeNode):\n",
    "    def __init__(self,val ,left=None,right=None,father=None):\n",
    "        self.val=val\n",
    "        self.left=left\n",
    "        self.right=right\n",
    "        self.father=father\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.p,self.q=None,None\n",
    "        head=TreeNode2(root.val)\n",
    "        t1=[root]\n",
    "        t2=[head]\n",
    "        while(len(t1)):\n",
    "            v1,v2=t1[0],t2[0]\n",
    "            t1,t2=t1[1:],t2[1:]\n",
    "\n",
    "            if v1.left:\n",
    "                v2.left=TreeNode2(v1.left.val)\n",
    "                v2.left.father=v2\n",
    "                t1.append(v1.left)\n",
    "                t2.append(v2.left)\n",
    "\n",
    "\n",
    "            if v1.right:\n",
    "                v2.right=TreeNode2(v1.right.val)\n",
    "                v2.right.father=v2\n",
    "                t1.append(v1.right)\n",
    "                t2.append(v2.right)\n",
    "            # print(v1.val,end=' ')\n",
    "            if v1==p:\n",
    "                self.p=v2\n",
    "            if v1==q:\n",
    "                self.q=v2\n",
    "            \n",
    "\n",
    "        p,q=self.p,self.q\n",
    "\n",
    "        res=[p]\n",
    "        # print(p.val,p.father.val,end=' ')\n",
    "\n",
    "        while(p!=head):\n",
    "            p=p.father\n",
    "            res.append(p)\n",
    "\n",
    "\n",
    "        # print(q.val,q.father.val)\n",
    "        while(q!=head):\n",
    "            if q in res:\n",
    "                return q\n",
    "            q=q.father\n",
    "        return head\n",
    "            \n",
    "\n",
    "    \n",
    "    def build(self,root,p,q):\n",
    "\n",
    "        if root==None:\n",
    "            return None\n",
    "\n",
    "        head=TreeNode2(root.val)\n",
    "        if root.left:\n",
    "            head.left=self.build(root.left,p,q)\n",
    "        if root.right:\n",
    "            head.right=self.build(root.right,p,q)\n",
    "        \n",
    "        if root==p:\n",
    "            self.p=head\n",
    "        if root==q:\n",
    "            self.q=head\n",
    "        \n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class TreeNode2(TreeNode):\n",
    "    def __init__(self,val ,left=None,right=None,father=None):\n",
    "        self.val=val\n",
    "        self.left=left\n",
    "        self.right=right\n",
    "        self.father=father\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.p,self.q=None,None\n",
    "        head=TreeNode2(root.val)\n",
    "        t1=[root]\n",
    "        t2=[head]\n",
    "        while(len(t1)):\n",
    "            v1,v2=t1[0],t2[0]\n",
    "            t1,t2=t1[1:],t2[1:]\n",
    "\n",
    "            if v1.left:\n",
    "                v2.left=TreeNode2(v1.left.val)\n",
    "                v2.left.father=v2\n",
    "                t1.append(v1.left)\n",
    "                t2.append(v2.left)\n",
    "\n",
    "\n",
    "            if v1.right:\n",
    "                v2.right=TreeNode2(v1.right.val)\n",
    "                v2.right.father=v2\n",
    "                t1.append(v1.right)\n",
    "                t2.append(v2.right)\n",
    "            # print(v1.val,end=' ')\n",
    "            if v1==p:\n",
    "                self.p=v2\n",
    "            if v1==q:\n",
    "                self.q=v2\n",
    "            \n",
    "\n",
    "        p,q=self.p,self.q\n",
    "\n",
    "        res=[p]\n",
    "        # print(p.val,p.father.val,end=' ')\n",
    "\n",
    "        while(p!=head):\n",
    "            p=p.father\n",
    "            res.append(p)\n",
    "\n",
    "\n",
    "        # print(q.val,q.father.val)\n",
    "        while(q!=head):\n",
    "            if q in res:\n",
    "                return q\n",
    "            q=q.father\n",
    "        return head\n",
    "            \n",
    "\n",
    "    \n",
    "    def build(self,root,p,q):\n",
    "\n",
    "        if root==None:\n",
    "            return None\n",
    "\n",
    "        head=TreeNode2(root.val)\n",
    "        if root.left:\n",
    "            head.left=self.build(root.left,p,q)\n",
    "        if root.right:\n",
    "            head.right=self.build(root.right,p,q)\n",
    "        \n",
    "        if root==p:\n",
    "            self.p=head\n",
    "        if root==q:\n",
    "            self.q=head\n",
    "        \n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not p or not q:return None\n",
    "        self.target={p.val,q.val}\n",
    "        return self.prior_traversal(root)\n",
    "    def prior_traversal(self,node):\n",
    "        # 如果是父子，那么返回先遇到的，没毛病\n",
    "        if not node or node.val in self.target:\n",
    "            return node# None,p,q\n",
    "        left=self.prior_traversal(node.left)\n",
    "        right=self.prior_traversal(node.right)\n",
    "        if left and right:# 两侧都检查完了\n",
    "            # 都是儿子\n",
    "            return node\n",
    "        elif left:\n",
    "            # 要返回父子必须把另外一边检查完了，没有另一个节点，这不如我的查到两个就直接返回快\n",
    "            return left\n",
    "        else:\n",
    "            return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.root = root\n",
    "        self.p = p\n",
    "        self.q = q\n",
    "        self.p_list = []\n",
    "        self.q_list = []\n",
    "        self.findNode(root,[])\n",
    "        index = 0\n",
    "        while index<len(self.p_list) and index<len(self.q_list):\n",
    "            if self.p_list[index]!=self.q_list[index]:\n",
    "                return self.p_list[index-1]\n",
    "            index+=1\n",
    "        return self.p_list[index-1]\n",
    "    def findNode(self,root,temp_list):\n",
    "        if root==None:return None\n",
    "        temp_list.append(root)\n",
    "        if root==self.p:\n",
    "            self.p_list = temp_list.copy()\n",
    "        elif root==self.q:\n",
    "            self.q_list = temp_list.copy()\n",
    "        if self.p_list==[] or self.q_list==[]:\n",
    "            self.findNode(root.left,temp_list)\n",
    "        if self.p_list==[] or self.q_list==[]:\n",
    "            self.findNode(root.right,temp_list)\n",
    "        temp_list.pop(-1)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.n1 = TreeNode(0)\n",
    "        self.n2 = TreeNode(0)\n",
    "        self.ancestor = None\n",
    "\n",
    "    def dfs_search_node(self, root: TreeNode):\n",
    "        if self.ancestor is None:\n",
    "            if root.left:\n",
    "                self.dfs_search_node(root.left)\n",
    "            if root.right:\n",
    "                self.dfs_search_node(root.right)\n",
    "            if root in (self.n1, self.n2):\n",
    "                if root.left in (self.n1, self.n2) or root.right in (self.n1, self.n2):\n",
    "                    self.ancestor = root\n",
    "            elif root.left in (self.n1, self.n2) and root.right in (self.n1, self.n2):\n",
    "                self.ancestor = root\n",
    "            elif self.n1 in (root.left, root.right):\n",
    "                self.n1 = root\n",
    "            elif self.n2 in (root.left, root.right):\n",
    "                self.n2 = root\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.n1 = p\n",
    "        self.n2 = q\n",
    "        self.dfs_search_node(root)\n",
    "        return self.ancestor\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.target = p.val\n",
    "        self.path = []\n",
    "        self.find_node(root)\n",
    "        p_path = self.path\n",
    "        p_path.reverse()\n",
    "\n",
    "        self.target = q.val\n",
    "        self.path = []\n",
    "        self.find_node(root)\n",
    "        q_path = self.path\n",
    "        q_path.reverse()\n",
    "\n",
    "        result = None\n",
    "        for i in range(min(len(p_path), len(q_path))):\n",
    "            if p_path[i].val == q_path[i].val:\n",
    "                result = p_path[i]\n",
    "        return result\n",
    "\n",
    "\n",
    "    def find_node(self, node: TreeNode):\n",
    "        if not node:\n",
    "            return False\n",
    "        if node.val == self.target:\n",
    "            self.path.append(node)\n",
    "            return True\n",
    "        if node.left and self.find_node(node.left):\n",
    "            self.path.append(node)\n",
    "            return True\n",
    "        if node.right and self.find_node(node.right):\n",
    "            self.path.append(node)\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    # 法一：使用辅助空间遍历二叉树两边得到两个链表来保存路径(从根开始), 再求两个链表的「最后一个」公共节点 \n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        l1, l2 = self.getPath(root, p), self.getPath(root, q)\n",
    "        i = 0\n",
    "        while  i < len(l1) and i < len(l2) and l1[i] == l2[i]: i += 1\n",
    "        return l1[i - 1]\n",
    "\n",
    "    def printPath(self):\n",
    "        print([x.val for x in self.path])\n",
    "\n",
    "    def getPath(self, root, target):\n",
    "        self.path = []\n",
    "        self.genPath(root, target)\n",
    "        self.printPath()\n",
    "        return self.path[:]\n",
    "\n",
    "    def genPath(self, root, target):   \n",
    "        if not root : return False   \n",
    "        self.path.append(root)\n",
    "        if root == target: return True\n",
    "        if self.genPath(root.left, target): return True\n",
    "        if self.genPath(root.right, target): return True\n",
    "        self.path.pop()\n",
    "        return False\n",
    "\n",
    "    # 愚蠢的方法： O(NlogN)\n",
    "    # def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "    #     def checkNumTarget(root, p, q):\n",
    "    #         if not root : return 0\n",
    "    #         if root.val == p.val or root.val == q.val:\n",
    "    #             sum = 1\n",
    "    #         else: sum = 0\n",
    "    #         return checkNumTarget(root.left, p, q) + checkNumTarget(root.right, p, q) + sum\n",
    "    #     if root.val == p.val or root.val == q.val: return root\n",
    "    #     if checkNumTarget(root.left, p, q) == checkNumTarget(root.right, p, q) == 1: return root\n",
    "    #     if checkNumTarget(root.left, p, q) == 2 : return self.lowestCommonAncestor(root.left, p, q)\n",
    "    #     if checkNumTarget(root.right, p, q) == 2 : return self.lowestCommonAncestor(root.right, p, q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return False\n",
    "        if root==p or root==q:\n",
    "            return root\n",
    "        l=self.lowestCommonAncestor(root.left,p,q)\n",
    "        r=self.lowestCommonAncestor(root.right,p,q)\n",
    "        if not l:\n",
    "            return r\n",
    "        if not r:\n",
    "            return l\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root == p or root == q:\n",
    "            return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if not left and not right:\n",
    "            return None\n",
    "        elif not left:\n",
    "            return right\n",
    "        elif not right:\n",
    "            return left\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        #方法一：编号\n",
    "        #为每个节点添加编号，root是pos，左孩子是2pos，右孩子是2pos+1，存到一个字典当中\n",
    "        #遍历过程中要检查是不是对p,q都编过号了，如果都编过了那我们也可以跳出遍历的循环了\n",
    "        #取出p和q的编号，当两者不相等时，编号较大者不断除2，直至二者相等，此时的值就是LCA的编号\n",
    "        #从字典中取出对应编号的key即可\n",
    "        if not root: return None\n",
    "        queue = [root]\n",
    "        dict = {root:1}\n",
    "        while queue :\n",
    "            node = queue.pop(0)\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "                dict[node.left] = 2*dict[node]\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "                dict[node.right] = 2*dict[node]+1\n",
    "            if p in dict and q in dict:\n",
    "                break\n",
    "        p0, q0 = dict[p], dict[q]\n",
    "        while p0 != q0:\n",
    "            if p0 > q0: p0//=2\n",
    "            else: q0//=2\n",
    "        for key,value in dict.items():\n",
    "            if value == p0: return key\n",
    "\n",
    "        #方法二：找路径\n",
    "        # if not root: return None\n",
    "        # queue = [[root,[root]]]\n",
    "        # pathp, pathq = [], []\n",
    "        # while queue:\n",
    "        #     node, path = queue.pop(0)\n",
    "        #     if node == p: pathp = path\n",
    "        #     if node == q: pathq = path\n",
    "        #     if node.left: queue.append([node.left, [node.left]+path])\n",
    "        #     if node.right: queue.append([node.right,[node.right]+path])\n",
    "        #     if pathp and pathq: break\n",
    "        # for node in pathp:\n",
    "        #     if node in pathq:\n",
    "        #         return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        #方法一：编号\n",
    "        #为每个节点添加编号，root是pos，左孩子是2pos，右孩子是2pos+1，存到一个字典当中\n",
    "        #遍历过程中要检查是不是对p,q都编过号了，如果都编过了那我们也可以跳出遍历的循环了\n",
    "        #取出p和q的编号，当两者不相等时，编号较大者不断除2，直至二者相等，此时的值就是LCA的编号\n",
    "        #从字典中取出对应编号的key即可\n",
    "        if not root: return None\n",
    "        queue = [root]\n",
    "        dict = {root:1}\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "                dict[node.left] = 2*dict[node]\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "                dict[node.right] = 2*dict[node]+1\n",
    "            if p in dict and q in dict:\n",
    "                break\n",
    "        p0, q0 = dict[p], dict[q]\n",
    "        while p0 != q0:\n",
    "            if p0 > q0: p0//=2\n",
    "            else: q0//=2\n",
    "        for key,value in dict.items():\n",
    "            if value == p0: return key\n",
    "\n",
    "        #方法二：找路径\n",
    "        # if not root: return None\n",
    "        # queue = [[root,[root]]]\n",
    "        # pathp, pathq = [], []\n",
    "        # while queue:\n",
    "        #     node, path = queue.pop(0)\n",
    "        #     if node == p: pathp = path\n",
    "        #     if node == q: pathq = path\n",
    "        #     if node.left: queue.append([node.left, [node.left]+path])\n",
    "        #     if node.right: queue.append([node.right,[node.right]+path])\n",
    "        #     if pathp and pathq: break\n",
    "        # for node in pathp:\n",
    "        #     if node in pathq:\n",
    "        #         return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        #方法一：编号\n",
    "        #为每个节点添加编号，root是pos，左孩子是2pos，右孩子是2pos+1，存到一个字典当中\n",
    "        #遍历过程中要检查是不是对p,q都编过号了，如果都编过了那我们也可以跳出遍历的循环了\n",
    "        #取出p和q的编号，当两者不相等时，编号较大者不断除2，直至二者相等，此时的值就是LCA的编号\n",
    "        #从字典中取出对应编号的key即可\n",
    "        if not root: return None\n",
    "        queue = [root]\n",
    "        dict = {root:1}\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "                dict[node.left] = 2*dict[node]\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "                dict[node.right] = 2*dict[node]+1\n",
    "            if p in dict and q in dict:\n",
    "                break\n",
    "        p0, q0 = dict[p], dict[q]\n",
    "        while p0 != q0:\n",
    "            if p0 > q0: p0//=2\n",
    "            else: q0//=2\n",
    "        for key,value in dict.items():\n",
    "            if value == p0: return key\n",
    "\n",
    "        #方法二：找路径\n",
    "        # if not root: return None\n",
    "        # queue = [[root,[root]]]\n",
    "        # pathp, pathq = [], []\n",
    "        # while queue:\n",
    "        #     node, path = queue.pop(0)\n",
    "        #     if node == p: pathp = path\n",
    "        #     if node == q: pathq = path\n",
    "        #     if node.left: queue.append([node.left, [node.left]+path])\n",
    "        #     if node.right: queue.append([node.right,[node.right]+path])\n",
    "        #     if pathp and pathq: break\n",
    "        # for node in pathp:\n",
    "        #     if node in pathq:\n",
    "        #         return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        #方法一：编号\n",
    "        #为每个节点添加编号，root是pos，左孩子是2pos，右孩子是2pos+1，存到一个字典当中\n",
    "        #遍历过程中要检查是不是对p,q都编过号了，如果都编过了那我们也可以跳出遍历的循环了\n",
    "        #取出p和q的编号，当两者不相等时，编号较大者不断除2，直至二者相等，此时的值就是LCA的编号\n",
    "        #从字典中取出对应编号的key即可\n",
    "        if not root: return None\n",
    "        queue = [root]\n",
    "        dict = {root:1}\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "                dict[node.left] = 2*dict[node]\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "                dict[node.right] = 2*dict[node]+1\n",
    "            if p in dict and q in dict:\n",
    "                break\n",
    "        p0, q0 = dict[p], dict[q]\n",
    "        while p0 != q0:\n",
    "            if p0 > q0: p0//=2\n",
    "            else: q0//=2\n",
    "        for key,value in dict.items():\n",
    "            if value == p0: return key\n",
    "\n",
    "        #方法二：找路径\n",
    "        # if not root: return None\n",
    "        # queue = [[root,[root]]]\n",
    "        # pathp, pathq = [], []\n",
    "        # while queue:\n",
    "        #     node, path = queue.pop(0)\n",
    "        #     if node == p: pathp = path\n",
    "        #     if node == q: pathq = path\n",
    "        #     if node.left: queue.append([node.left, [node.left]+path])\n",
    "        #     if node.right: queue.append([node.right,[node.right]+path])\n",
    "        #     if pathp and pathq: break\n",
    "        # for node in pathp:\n",
    "        #     if node in pathq:\n",
    "        #         return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.parent = {}\n",
    "        self.traverse(root)\n",
    "        p_path = [id(p)]\n",
    "        while id(p) in self.parent:\n",
    "            p = self.parent[id(p)]\n",
    "            p_path.append(id(p))\n",
    "        while id(q) not in p_path:\n",
    "            q = self.parent[id(q)]\n",
    "        return q\n",
    "    def traverse(self,root):\n",
    "        if root.left:\n",
    "            self.parent[id(root.left)] = root\n",
    "            self.traverse(root.left)\n",
    "        if root.right:\n",
    "            self.parent[id(root.right)] = root\n",
    "            self.traverse(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root==p or root==q:return root\n",
    "        left=self.lowestCommonAncestor(root.left,p,q)\n",
    "        right=self.lowestCommonAncestor(root.right,p,q)\n",
    "        if not left:return right\n",
    "        if not right:return left\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root.val == p.val or root.val == q.val:\n",
    "            return root\n",
    "        left = self.lowestCommonAncestor(root.left, p,q)\n",
    "        right = self.lowestCommonAncestor(root.right,p,q)\n",
    "        if not left and not right:\n",
    "            return\n",
    "        if not left:\n",
    "            return right\n",
    "        if not right:\n",
    "            return left\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root.val == p.val or root.val == q.val:\n",
    "            return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if not left: return right\n",
    "        if not right: return left\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "\n",
    "        # ans = collections.defaultdict(list)\n",
    "\n",
    "        # def dfs(node, parents, tar):\n",
    "        #     if not node:\n",
    "        #         return\n",
    "        #     if node.val == tar:\n",
    "        #         ans[node.val] = parents + [node.val]\n",
    "        #     dfs(node.left, parents + [node.val], tar)\n",
    "        #     dfs(node.right, parents + [node.val], tar)\n",
    "        \n",
    "        # dfs(root, [], p.val)\n",
    "        # dfs(root, [], q.val)\n",
    "        # tar = []\n",
    "        # def find(node, t):\n",
    "        #     if not node:\n",
    "        #         return\n",
    "        #     if node.val == t:\n",
    "        #         tar.append(node)\n",
    "        #         return\n",
    "        #     find(node.left, t)\n",
    "        #     find(node.right, t)\n",
    "        # for i in ans[p.val][::-1]:\n",
    "        #     for j in ans[q.val][::-1]:\n",
    "        #         if i == j:\n",
    "        #             find(root, i)\n",
    "        #             return tar[0]\n",
    "        if not root or root == p or root == q: return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if not left: return right\n",
    "        if not right: return left\n",
    "        return root\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def DFS_find_node(self, root, target, path):\n",
    "        if root == None:return False\n",
    "\n",
    "        if root.val == target :return [root]\n",
    "        # 如果左右节点 任何一个节点 有目标 路径 就把当前节点添加进路径 否则不添加\n",
    "        if root.left!=None:\n",
    "            tmp_p = self.DFS_find_node(root.left, target, path)\n",
    "            if tmp_p!=[]:\n",
    "                tmp_p.append(root)\n",
    "                return tmp_p\n",
    "        if root.right!=None:\n",
    "            tmp_p = self.DFS_find_node(root.right, target, path)\n",
    "            if tmp_p!=[]:\n",
    "                tmp_p.append(root)\n",
    "                return tmp_p\n",
    "        return []\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        # 先用DFS找到 包涵 p q的 从root到 p q的 通路 并且写入数组\n",
    "        # 再判定 两者最近的联通情况\n",
    "        p_path = self.DFS_find_node(root,p.val,[])\n",
    "        q_path = self.DFS_find_node(root,q.val,[])\n",
    "        #print(p_path)\n",
    "        #print(q_path)\n",
    "\n",
    "        # 从上向下找一样的元素 最后一个即为最近公共了\n",
    "        both_path = []\n",
    "        while p_path!=[] and q_path!=[]:\n",
    "            p_n = p_path.pop()\n",
    "            q_n = q_path.pop()\n",
    "            if p_n.val == q_n.val:\n",
    "                both_path.append(p_n)\n",
    "        return both_path[-1]\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getPath(self,root,p):\n",
    "        path = []\n",
    "        if root == None:\n",
    "            return path\n",
    "        if root is p:\n",
    "            path.append(root)\n",
    "            return path\n",
    "        pathLeft = self.getPath(root.left,p)\n",
    "        if pathLeft:\n",
    "            path.append(root)\n",
    "            path.extend(pathLeft)\n",
    "            return path\n",
    "        else:\n",
    "            pathRight = self.getPath(root.right,p)\n",
    "            if pathRight:\n",
    "                path.append(root)\n",
    "                path.extend(pathRight)\n",
    "                return path\n",
    "            else:\n",
    "                return path\n",
    "\n",
    "\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        pathP = self.getPath(root,p)\n",
    "        pathQ = self.getPath(root,q)\n",
    "        i = 0\n",
    "        while i < min(len(pathP),len(pathQ)) and pathP[i] is pathQ[i]:\n",
    "            i = i + 1\n",
    "        return pathP[i - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = None\n",
    "        self.p =None\n",
    "        self.q = None\n",
    "    def findlist(self,now_root):\n",
    "        flag = 0\n",
    "        if(now_root==None):\n",
    "            return 0\n",
    "        flag +=self.findlist(now_root.left)\n",
    "        flag +=self.findlist(now_root.right)\n",
    "        if(now_root.val==self.p.val):\n",
    "            flag = flag+1\n",
    "        elif(now_root.val==self.q.val):\n",
    "            flag = flag+1\n",
    "\n",
    "        if((flag==2)&(self.result==None)):\n",
    "            self.result = now_root\n",
    "        return flag\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.p = p\n",
    "        self.q = q \n",
    "        self.findlist(root)\n",
    "        return self.result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.p = None\n",
    "        self.q = None\n",
    "        self.out = None\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.p = p\n",
    "        self.q = q\n",
    "        self.recur(root)\n",
    "        return self.out\n",
    "\n",
    "\n",
    "\n",
    "    def recur(self,root):\n",
    "        if self.out != None:\n",
    "            return True\n",
    "        if root ==None:\n",
    "            return False\n",
    "\n",
    "        left = self.recur(root.left)\n",
    "        right = self.recur(root.right)\n",
    "\n",
    "        if root.val==self.p.val or root.val==self.q.val:\n",
    "            if left or right and self.out==None:#祖先为自己\n",
    "                self.out = root\n",
    "            return True\n",
    "        else:\n",
    "            if left and right and self.out==None:#左右都可以了\n",
    "                self.out = root\n",
    "        return left or right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.ans =  None\n",
    "        self.p = p\n",
    "        self.q = q\n",
    "        self.help(root)\n",
    "        return self.ans\n",
    "\n",
    "    def help(self,root):\n",
    "\n",
    "        if root is None:\n",
    "            return False\n",
    "        \n",
    "        f_l = self.help(root.left)\n",
    "        f_r = self.help(root.right)\n",
    "        if f_r and f_l and self.ans is None:\n",
    "            self.ans = root\n",
    "            return True\n",
    "        if root == self.p or root == self.q:\n",
    "            if f_r or f_l and self.ans is None:\n",
    "                self.ans = root\n",
    "            return True\n",
    "\n",
    "        if f_l or f_r:\n",
    "            return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.output = None\n",
    "        self.p = p\n",
    "        self.q = q\n",
    "        self.search(root)\n",
    "        return self.output\n",
    "\n",
    "    def search(self, node):\n",
    "        if not node:\n",
    "            return False\n",
    "\n",
    "        left = self.search(node.left)\n",
    "        right = self.search(node.right)\n",
    "\n",
    "        if left and right:\n",
    "            self.output = node\n",
    "            return True\n",
    "        elif (node == self.q or node == self.p) and (left or right):\n",
    "            self.output = node\n",
    "            return True\n",
    "        else:\n",
    "            return left or right or node == self.p or node == self.q\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root: \n",
    "            return None\n",
    "        val_idx = defaultdict(int)\n",
    "        idx_TreeNode = defaultdict(TreeNode)\n",
    "        que = deque()\n",
    "        que.append(root)\n",
    "        idx = 1\n",
    "        val_idx[root.val] = idx\n",
    "\n",
    "        while que:\n",
    "            n = len(que)\n",
    "            while n:\n",
    "                cur = que.popleft()\n",
    "                cur_idx = val_idx[cur.val]\n",
    "                idx_TreeNode[cur_idx] = cur\n",
    "                if cur.left:\n",
    "                    que.append(cur.left)\n",
    "                    val_idx[cur.left.val] = 2 * cur_idx\n",
    "                if cur.right:\n",
    "                    que.append(cur.right)\n",
    "                    val_idx[cur.right.val] = 2 * cur_idx + 1\n",
    "                n -= 1\n",
    "        p_idx = val_idx[p.val]\n",
    "        q_idx = val_idx[q.val]\n",
    "        while p_idx != q_idx:\n",
    "            while p_idx > q_idx:\n",
    "                p_idx //= 2\n",
    "            while q_idx > p_idx:\n",
    "                q_idx //= 2\n",
    "        return idx_TreeNode[p_idx]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.p=p\n",
    "        self.q=q\n",
    "        return self.find(root)\n",
    "    def find(self,root):\n",
    "        left=None\n",
    "        right=None\n",
    "        if not root:\n",
    "            return None\n",
    "        if root==self.p or root==self.q:\n",
    "            return root\n",
    "        if root.left:\n",
    "            left=self.find(root.left)\n",
    "            #print(left)\n",
    "            #print(root)\n",
    "        if root.right:\n",
    "            right=self.find(root.right)\n",
    "            #print(right)\n",
    "            #print(root)\n",
    "        if not root.left and not root.right:\n",
    "            return None\n",
    "        if left and right:\n",
    "            return root\n",
    "        elif not left:\n",
    "            return right \n",
    "        elif not right:\n",
    "            return left \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.fa = {}\n",
    "        self.vis = {}\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.fa[root.val] = None\n",
    "        self.dfs(root)\n",
    "        while p != None:\n",
    "            self.vis[p.val] = True\n",
    "            p = self.fa[p.val]\n",
    "        \n",
    "        while q != None:\n",
    "            if q.val in self.vis and self.vis[q.val]:\n",
    "                return q\n",
    "            q = self.fa[q.val]\n",
    "        return None\n",
    "\n",
    "    def dfs(self, root):\n",
    "        if root.left != None:\n",
    "            self.fa[root.left.val] = root\n",
    "            self.dfs(root.left)\n",
    "        \n",
    "        if root.right != None:\n",
    "            self.fa[root.right.val] = root\n",
    "            self.dfs(root.right)\n",
    "\n",
    "# class Solution:\n",
    "#     def __init__(self):\n",
    "#         self.ans = None\n",
    "#     def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "     \n",
    "#         self.dfs(root, p, q)\n",
    "#         return self.ans\n",
    "\n",
    "#     def dfs(self, root, p, q):\n",
    "#         if root == None:\n",
    "#             return False\n",
    "#         lson = self.dfs(root.left, p, q)\n",
    "#         rson = self.dfs(root.right, p, q)\n",
    "#         if (lson and rson) or (root.val == p.val or root.val == q.val) and (lson or rson):\n",
    "#             self.ans = root\n",
    "\n",
    "#         return lson or rson or (root.val == p.val or root.val == q.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root: return\n",
    "\n",
    "        father_dict = {}\n",
    "        father_dict[root] = root\n",
    "        self.process(root, father_dict)\n",
    "\n",
    "        p_father = set()\n",
    "        while p != father_dict[p]:\n",
    "            p_father.add(p)\n",
    "            p = father_dict[p]\n",
    "        p_father.add(root)\n",
    "\n",
    "        while q != father_dict[q]:\n",
    "            if q in p_father:\n",
    "                return q\n",
    "            else:\n",
    "                q = father_dict[q]\n",
    "        return root\n",
    "\n",
    "\n",
    "    def process(self, root, father_dict):\n",
    "        if not root: return \n",
    "        father_dict[root.left] = root\n",
    "        father_dict[root.right] = root\n",
    "        self.process(root.left, father_dict)\n",
    "        self.process(root.right, father_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return root\n",
    "        if root == p or root == q:\n",
    "            return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if left and right:\n",
    "            return root\n",
    "        if left:\n",
    "            return left\n",
    "        if right:\n",
    "            return right\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root == p or root == q: return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if not left and not right: return\n",
    "        if not left: return right\n",
    "        if not right: return left\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, root, p, q):\n",
    "        if not root:\n",
    "            return root\n",
    "        if root == p or root == q:\n",
    "            return root\n",
    "        left = self.dfs(root.left, p, q)\n",
    "        right = self.dfs(root.right, p, q)\n",
    "        if not left and not right:\n",
    "            return # 情况1\n",
    "\n",
    "        if not left:\n",
    "            return right\n",
    "        if not right:\n",
    "            return left\n",
    "        return root  # 情况2\n",
    "            \n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.res = None\n",
    "        \n",
    "        return self.dfs(root, p, q)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root == p or root == q: return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if not left and not right: return None # 1.\n",
    "        if not left: return right # 3.\n",
    "        if not right: return left # 4.\n",
    "        return root # 2. if left and right:  \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root == p or root == q: return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if not left: return right\n",
    "        if not right: return left\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or p==root or q==root:\n",
    "            return root\n",
    "        l=self.lowestCommonAncestor(root.left,p,q)\n",
    "        r=self.lowestCommonAncestor(root.right,p,q)\n",
    "        print(l)\n",
    "        print(r)\n",
    "        print('..................')\n",
    "        if not l:\n",
    "            return r\n",
    "        if not r:\n",
    "            return l\n",
    "        return root\n",
    "\n",
    "#  如果左子树的祖先空，则返回右子树找到的祖先\n",
    "# 如果右子树的祖先空，则返回左子树找打的祖先\n",
    "# 如果左右子树的祖先非空,返回当前root\n",
    "    # 1、 如果结点 p、q 都存在且为左右结点，那么根结点 root 就是最近公共祖先；\n",
    "    # 2、 如果结点 p、q 都存在且都为左结点，那么在根结点 root 的左子树查找；\n",
    "    # 3、 如果结点 p、q 都存在且都为右结点，那么在根结点 root 的右子树查找。\n",
    "    # 边界条件\n",
    "    # 1、 空树；\n",
    "    # 2、 p 为根结点 root;\n",
    "    # 3、 q 为根结点 root。\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def search(self, root: TreeNode, p: TreeNode) -> List:\n",
    "        if not root:\n",
    "            return []\n",
    "        else:\n",
    "            if root.val == p.val:\n",
    "                return [root]\n",
    "            else:\n",
    "                a = self.search(root.left,p)\n",
    "                b = self.search(root.right,p)\n",
    "                if a:\n",
    "                    return a+[root]\n",
    "                elif b:\n",
    "                    return b+[root]\n",
    "                else:\n",
    "                    return []\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return root\n",
    "        find_p = self.search(root,p)\n",
    "        find_q = self.search(root,q)\n",
    "        for i in find_p:\n",
    "            if i in find_q:\n",
    "                return i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.dfs(root, p, q)\n",
    "        return self.node\n",
    "        \n",
    "    def dfs(self, root, p, q):\n",
    "        # return p_visited, q_visited\n",
    "        if not root:\n",
    "            return False, False\n",
    "\n",
    "        p_visited_left, q_visited_left = self.dfs(root.left, p, q)\n",
    "        if p_visited_left and q_visited_left:\n",
    "            return True, True\n",
    "\n",
    "        p_visited_right, q_visited_right = self.dfs(root.right, p, q)\n",
    "        if p_visited_right and q_visited_right:\n",
    "            return True, True\n",
    "\n",
    "        p_visited = p_visited_left or p_visited_right or p == root\n",
    "        q_visited = q_visited_left or q_visited_right or q == root\n",
    "        if p_visited and q_visited:\n",
    "            self.node = root\n",
    "\n",
    "        return p_visited, q_visited\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.res = None\n",
    "        self.find(root, p, q)\n",
    "        return self.res\n",
    "\n",
    "    def find(self, root, p, q):\n",
    "        if not root:\n",
    "            return False, False\n",
    "\n",
    "        has_p_l, has_q_l = self.find(root.left, p, q)\n",
    "        has_p_r, has_q_r = self.find(root.right , p, q)\n",
    "        \n",
    "        has_p, has_q =  root == p, root == q\n",
    "        has_p = has_p or has_p_l or has_p_r\n",
    "        has_q = has_q or has_q_l or has_q_r\n",
    "        if has_p and has_q:\n",
    "            if not self.res:\n",
    "                self.res = root\n",
    "            # return True, True\n",
    "\n",
    "        return has_p, has_q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root == p or root == q:\n",
    "            return root\n",
    "        root.left = self.lowestCommonAncestor(root.left,p,q)\n",
    "        root.right = self.lowestCommonAncestor(root.right,p,q)\n",
    "        if not root.left:\n",
    "            return root.right\n",
    "        if not root.right:\n",
    "            return root.left\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            \n",
    "            if node == p or node == q:\n",
    "                return node\n",
    "            \n",
    "            left_tree = dfs(node.left)\n",
    "            right_tree = dfs(node.right)\n",
    "\n",
    "            if left_tree and right_tree:\n",
    "                return node\n",
    "\n",
    "            if left_tree:\n",
    "                return left_tree\n",
    "\n",
    "            if right_tree:\n",
    "                return right_tree\n",
    "            \n",
    "            return None\n",
    "\n",
    "        return dfs(root)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        def recur(node):\n",
    "            if node is None:\n",
    "                return None\n",
    "            if node.val == p.val or node.val == q.val:\n",
    "                return node\n",
    "            node.left = recur(node.left)\n",
    "            node.right = recur(node.right)\n",
    "            if node.left is None and node.right is None:\n",
    "                return None\n",
    "            if node.left and node.right:\n",
    "                return node\n",
    "            if node.left is None:\n",
    "                return node.right\n",
    "            if node.right is None:\n",
    "                return node.left\n",
    "        res = recur(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        dict_target = {p,q}\n",
    "\n",
    "        def helper(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            elif node in dict_target:\n",
    "                res_l = helper(node.left)\n",
    "                res_r = helper(node.right) \n",
    "                return node\n",
    "            else:\n",
    "                res_l = helper(node.left)\n",
    "                res_r = helper(node.right) \n",
    "                if (res_l in dict_target and res_r in dict_target) :\n",
    "                    return node\n",
    "                return res_l if res_l else res_r        \n",
    "        return helper(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root == p or root == q:\n",
    "            return root\n",
    "\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "\n",
    "        if left and right:\n",
    "            return root\n",
    "\n",
    "        if left:\n",
    "            return left\n",
    "\n",
    "        if right:\n",
    "            return right\n",
    "\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root == p or root == q: return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if not left: return right\n",
    "        if not right: return left\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "\n",
    "\n",
    "\n",
    "        def tree(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            if root in [p,q]:\n",
    "                return root\n",
    "            l=tree(root.left)\n",
    "            r=tree(root.right)\n",
    "            if l and r:\n",
    "                return root\n",
    "            elif l:\n",
    "                return l\n",
    "            else:\n",
    "                return r\n",
    "        return tree(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        def dfs(node, p, q):\n",
    "            if not node:\n",
    "                return None\n",
    "            if node == p or node == q:\n",
    "                return node\n",
    "            left = dfs(node.left, p, q)\n",
    "            right = dfs(node.right, p, q)\n",
    "\n",
    "            if not left and not right:\n",
    "                return None\n",
    "            if not left:\n",
    "                return right\n",
    "            if not right:\n",
    "                return left\n",
    "            return node\n",
    "        \n",
    "        return dfs(root, p, q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root.val == p.val or root.val == q.val:\n",
    "            return root\n",
    "        l, r = self.lowestCommonAncestor(root.left, p, q), self.lowestCommonAncestor(root.right, p, q)\n",
    "        return root if l and r else l or r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self,root,p,q):\n",
    "        if not root :\n",
    "            return \n",
    "        self.nodes.append(root)\n",
    "        self.dfs(root.left,p,q)\n",
    "        self.dfs(root.right,p,q)\n",
    "        node=self.nodes.pop()\n",
    "        if node.val==p.val:\n",
    "            self.p_path=self.nodes.copy()\n",
    "            self.p_path.append(node)\n",
    "        elif node.val==q.val:\n",
    "            self.q_path=self.nodes.copy()\n",
    "            self.q_path.append(node)\n",
    "\n",
    "\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        self.nodes=[]\n",
    "        self.p_path=None\n",
    "        self.q_path=None\n",
    "        self.dfs(root,p,q)\n",
    "        i=len(self.p_path)-1\n",
    "        while i>=0:\n",
    "            node=self.p_path[i]\n",
    "            if node in self.q_path:\n",
    "                return node\n",
    "            i-=1\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        def dfso(root, p):\n",
    "            if root is None:\n",
    "                return False\n",
    "            pf = root==p\n",
    "            return pf or dfso(root.left, p) or dfso(root.right, p)\n",
    "\n",
    "        def dfs(root, p, q):\n",
    "            if root is None:\n",
    "                return False, False\n",
    "            if root==p and root==q:\n",
    "                self.res=root\n",
    "                return True, True\n",
    "            elif root==p:\n",
    "                f = dfso(root.left, q) or dfso(root.right, q)\n",
    "                if f:self.res=root\n",
    "                return True, f\n",
    "            elif root==q:\n",
    "                f=dfso(root.left, p) or dfso(root.right, p)\n",
    "                if f: self.res=root\n",
    "                return f, True\n",
    "            else:\n",
    "                fl1, fl2 = dfs(root.left, p, q)\n",
    "                if self.res is None:\n",
    "                    if fl1:\n",
    "                        fr2 = dfso(root.right, q)\n",
    "                        if fr2:\n",
    "                            self.res = root\n",
    "                        return fl1, fr2\n",
    "                    elif fl2:\n",
    "                        fr1 = dfso(root.right, p)\n",
    "                        if fr1:\n",
    "                            self.res = root\n",
    "                        return fr1, fl2\n",
    "                    # elif fl1 and fl2:\n",
    "                    #     self.res=root.left\n",
    "                    #     return True, True\n",
    "                    else:\n",
    "                        return dfs(root.right, p, q)\n",
    "                return fl1, fl2\n",
    "            \n",
    "        self.res=None\n",
    "        dfs(root, p, q)\n",
    "        return self.res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def reg(self, root, p, q):\n",
    "        if root is None:\n",
    "            return False, False\n",
    "        findP, findQ = False, False\n",
    "        if root == p:\n",
    "            findP = True\n",
    "        if root == q:\n",
    "            findQ = True\n",
    "        fp1, fq1 = self.reg(root.left, p, q)\n",
    "        findP = findP or fp1\n",
    "        findQ = findQ or fq1\n",
    "        if findP and findQ:\n",
    "            if self.res is None:\n",
    "                self.res = root\n",
    "            return True, True\n",
    "        fp2, fq2 = self.reg(root.right, p, q)\n",
    "        findP = findP or fp2\n",
    "        findQ = findQ or fq2\n",
    "        if findP and findQ:\n",
    "            if self.res is None:\n",
    "                self.res = root\n",
    "            return True, True\n",
    "        return findP, findQ\n",
    "\n",
    "        \n",
    "\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.res = None\n",
    "        self.reg(root, p, q)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "\n",
    "        if not root: return \n",
    "\n",
    "        self.p_val = p.val\n",
    "        self.q_val = q.val\n",
    "\n",
    "\n",
    "        def recur (in_node):\n",
    "            if not in_node: return None\n",
    "            if in_node.val == self.p_val:\n",
    "                return in_node\n",
    "            if in_node.val == self.q_val:\n",
    "                return in_node\n",
    "            l = recur(in_node.left)\n",
    "            r = recur(in_node.right)\n",
    "            if l and r:\n",
    "                return in_node\n",
    "            if l or r:\n",
    "                if l != None:\n",
    "                    return l\n",
    "                else: \n",
    "                    return r\n",
    "            if not l and not r:\n",
    "                return None\n",
    "        \n",
    "        return recur(root)\n",
    "\n",
    "\n",
    "\n",
    "        # if not root: return \n",
    "\n",
    "        # self.found = 0\n",
    "        # self.family = []\n",
    "        # self.target = p.val\n",
    "\n",
    "        # def recur (in_node):\n",
    "        #     if not in_node: return\n",
    "        #     if in_node.val == self.target:\n",
    "        #         self.found = 1\n",
    "        #         self.family.append(in_node)\n",
    "        #         return\n",
    "        #     recur(in_node.left)\n",
    "        #     if self.found: \n",
    "        #         self.family.insert(0, in_node)\n",
    "        #         return\n",
    "        #     recur(in_node.right)\n",
    "        #     if self.found: \n",
    "        #         self.family.insert(0, in_node)\n",
    "        #         return\n",
    "        \n",
    "        # recur(root)\n",
    "        # p_family = self.family\n",
    "\n",
    "        # self.found = 0\n",
    "        # self.family = []\n",
    "        # self.target = q.val\n",
    "\n",
    "        # recur(root)\n",
    "        # q_family = self.family\n",
    "        # # print(p_family)\n",
    "        # # print(q_family)\n",
    "\n",
    "        # for i in range(min(len(q_family), len(p_family))):\n",
    "        #     if p_family[i].val != q_family[i].val:\n",
    "        #         return p_family[i-1]\n",
    "        \n",
    "        # if len(q_family) <= len(p_family):\n",
    "        #     return q_family[-1]\n",
    "        # if len(q_family) > len(p_family):\n",
    "        #     return p_family[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root == p or root == q: return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if not left and not right: return # 1.\n",
    "        if not left: return right # 3.\n",
    "        if not right: return left # 4.\n",
    "        return root # 2. if left and right:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root == p or root == q:\n",
    "            return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if not left:\n",
    "            return right\n",
    "        if not right:\n",
    "            return left\n",
    "        return root\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root == p or root == q: return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if not left: return right\n",
    "        if not right: return left\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root == p or root == q: return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if not left: return right\n",
    "        if not right: return left\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root.val == p.val or root.val == q.val:return root\n",
    "        left = self.lowestCommonAncestor(root.left,p,q)\n",
    "        right = self.lowestCommonAncestor(root.right,p,q)\n",
    "        if not left:return right\n",
    "        if not right:return left\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        # If looking for me, return myself\n",
    "        if root is None or root == p or root == q:\n",
    "            return root\n",
    "\n",
    "        # Look for keys in left and right subtrees\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "\n",
    "        # If both left and right are not None, this is the LCA\n",
    "        if left is not None and right is not None:\n",
    "            return root\n",
    "\n",
    "        # Otherwise return the non-None child\n",
    "        return left if left is not None else right\n",
    "\n",
    "# Helper function to build tree from list input\n",
    "def build_tree(list_vals):\n",
    "    if not list_vals:\n",
    "        return None\n",
    "    \n",
    "    # Create a list of trees\n",
    "    nodes = [TreeNode(x) if x is not None else None for x in list_vals]\n",
    "    \n",
    "    # List to keep track of nodes which haven't been assigned a parent yet\n",
    "    kids = nodes[::-1]\n",
    "    \n",
    "    # The last node is the first to be popped, it's the root node\n",
    "    root = kids.pop()\n",
    "    \n",
    "    for node in nodes:\n",
    "        if node:\n",
    "            if kids: node.left = kids.pop()\n",
    "            if kids: node.right = kids.pop()\n",
    "    return root\n",
    "\n",
    "# Given test case\n",
    "list_vals = [3,5,1,6,2,0,8,None,None,7,4]\n",
    "root = build_tree(list_vals)\n",
    "\n",
    "# The function does not actually search by value, so we need to provide nodes directly\n",
    "p = root.left  # Node with value 5\n",
    "q = root.right  # Node with value 1\n",
    "\n",
    "# Create a Solution instance and find the LCA\n",
    "sol = Solution()\n",
    "lca = sol.lowestCommonAncestor(root, p, q)\n",
    "\n",
    "# Output the value of the LCA\n",
    "lca.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.ans=None\n",
    "        self.CommonAncestor(root,p,q)\n",
    "        return self.ans\n",
    "    \n",
    "    def CommonAncestor(self,root,p,q):\n",
    "        # if root: print(root.val)\n",
    "        if self.ans is not None: return False,False\n",
    "        if not root:\n",
    "            return False,False\n",
    "        \n",
    "        Lp,Lq=self.CommonAncestor(root.left,p,q)\n",
    "        Rp,Rq=self.CommonAncestor(root.right,p,q)\n",
    "        RTp = Lp or Rp or root==p\n",
    "        RTq = Lq or Rq or root==q\n",
    "        if not self.ans and RTp and RTq:\n",
    "            self.ans=root\n",
    "        return RTp,RTq\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def traverseNode(self, root: TreeNode, p: TreeNode, q: TreeNode):\n",
    "        if root == None:\n",
    "            return None,0\n",
    "        left,left_num = self.traverseNode(root.left,p,q)\n",
    "        if left_num ==2:\n",
    "            return left,2\n",
    "        right,right_num = self.traverseNode(root.right,p,q)\n",
    "        if right_num ==2:\n",
    "            return right,2\n",
    "        n = 1 if root.val == p.val  or root.val == q.val else 0\n",
    "        n = n + left_num+right_num\n",
    "        return root,n\n",
    "\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        ans,_  = self.traverseNode(root,p,q)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
